package com.nanbei.tree;

import org.junit.Test;

import java.security.PublicKey;

/**
 * @ClassDescription: 二叉搜索树
 * @JdkVersion: 17
 * @Author: BaoShan.li
 * @Created: 2023/12/18 14:03
 */
public class BSTree {

    BSTNode root;

    public BSTree(BSTNode root) {
        this.root = root;
    }

    /**
     * 根据key查找值
     * @param key 键
     * @return 值
     */
    public  Object get(int key){

        BSTNode node = root;

        while (node!=null){
            if (key > node.key){
                node = node.right;
            }else if (key < node.key){
                node = node.left;
            }else {
                return node.value;
            }
        }
        return null;
    }

    /**
     * 获取二叉搜索树最大值
     * @return 值
     */
    public  Object getMax(){
        return doMax(root);
    }

    private Object doMax(BSTNode root){
        BSTNode node = root;

        while (node.right!=null){
            node = node.right;
        }
        return node.value;
    }

    /**
     * 获取二叉搜索树最大值
     * @return 值
     */
    public  Object getMin(){
        return doMin(root);
    }

    private Object doMin(BSTNode root){
        BSTNode node = root;

        while (node.left!=null){
            node = node.left;
        }
        return node.value;
    }

    /**
     * 向树中插入值
     * @param key 键
     * @param value 值
     * @return 值
     */
    public boolean put(int key,Object value){

        if (root == null){
            root = new BSTNode(key,value);
            return true;
        }

        BSTNode node = root;
        BSTNode parent = null;
        while (node!=null){
            parent = node;
            if (key > node.key){
                node = node.right;
            }else if (key<node.key){
                node = node.left;
            }else {
                node.value = value;
                return true;
            }
        }

        // 在树中未找到相对应的key 需要向树中插入
        // key小于父节点的key 则插入根节点的左边
        if (key < parent.key){
            parent.left = new BSTNode(key,value);
        }else {
            // key大于父节点的key 则插入根节点的右边
            parent.right = new BSTNode(key,value);
        }
        return true;
    }

    /**
     * 查找前驱节点
     * @param key 待查找的值
     * @return key的前驱节点
     */
    public Object predecessor(int key){

        BSTNode node = root;
        BSTNode grand = null;
        while (node!=null){
            if (key > node.key){
                grand = node;
                node = node.right;
            }else if (key<node.key){
                node = node.left;
            }else {
               break;
            }
        }

        if (node == null){
            return null;
        }

        if (node.left != null){
            return doMax(node.left);
        }else {
            return grand == null ? null : grand.value;
        }
    }


    /**
     * 查找后继节点
     * @param key 待查找的值
     * @return key的后继节点
     */
    public Object successor(int key){
        if (root == null){
            return null;
        }

        BSTNode node = root;
        BSTNode grand = null;
        while (node!=null){
            if (key > node.key){
                node = node.right;
            }else if (key<node.key){
                grand = node;
                node = node.left;
            }else {
                break;
            }
        }

        if (node == null){
            return null;
        }

        if (node.right != null){
            return doMin(node.left);
        }else {
            return grand == null ? null : grand.value;
        }
    }


    /**
     * 删除节点：
     *  1.删除的节点没有左孩子，将右孩子托孤给Parent
     *  2.删除的节点没有右孩子，将左孩子托孤给Parent
     * @param key 需要删除的键
     */
    public BSTNode deleteNode(int key){
        BSTNode node = root;
        BSTNode parent = null;
        while (node != null){
            if (key > node.key){
                parent = node;
                node = node.right;
            }else if (key < node.key){
                parent = node;
                node = node.left;
            }else {
                break;
            }
        }

        if (node == null) {
            return null;
        }


        if (node.left == null && node.right != null ){
            //  删除的节点没有左孩子，将右孩子托孤给Parent
            shift(parent,node,node.right);
        } else if (node.right == null && node.left != null) {
            // 删除的节点没有右孩子，将左孩子托孤给Parent
            shift(parent,node,node.left);
        }else {
            // 删除的节点既有左孩子又有右孩子
            BSTNode successor = node.right;
            BSTNode parentSuccessor = node;
            while (successor.left != null){
                parentSuccessor = successor;
                successor = successor.left;
            }
            if (parentSuccessor != node){
                shift(parentSuccessor,successor,successor.right);
                successor.right = node.right;
            }
            shift(parent,node,successor);
            successor.left = node.left;

        }
        return null;
    }

    /**
     *  托孤方法
     * @param parent 被删除节点的父亲
     * @param deleted 被删除的节点
     * @param child 被顶上去的节点
     */
    public void shift(BSTNode parent,BSTNode deleted,BSTNode child){
        if (parent == null){
            root = child;
        }else if (deleted  == parent.left){
            parent.left = child;
        }else {
            parent.right = child;
        }
    }

    /**
     *  使用递归方法删除key
     * @param key 要被删除的键
     */
    public void delete(int key){
        root = doDelete(root, key);
    }

    public BSTNode doDelete(BSTNode root, int key) {
        if (root == null) {
            return null;
        }

        if (key > root.key) {
            root.right = doDelete(root.right, key);
            return root;
        } else if (key < root.key) {
            root.left = doDelete(root.left, key);
            return root;
        } else {
            if (root.right == null) {
                return root.left;
            } else if (root.left == null) {
                return root.right;
            } else {
                BSTNode sp = root.right;
                while (sp.left != null) {
                    sp = sp.left;
                }
                sp.right = doDelete(root.right, sp.key);
                sp.left = root.left;
                return sp;
            }
        }
    }




}
